#include<vector>
#include<iostream>
using namespace std;

class DocumentSearch
{
	public:
	int nonIntersecting(vector <string> doc, string search)
	{
		int i=0,j=0;
		int *a = new int[search.length()];
		int counter =0;
		while(i<doc.size())
		{
			int k=0;
			while(k<doc[i].length())
			{
				if(doc[i][k] == search[j])
				{
					if(j == search.length()-1)
					{
						counter++;
						j=0;
						k++;
					}
					else
					{
						k++;
						j++;
					}
				}
				else
				{
					j = a[j-1];
					k++;
				}
			}
			i++;
		}
		delete[] a;
		return counter;
	}
	

	private:
	void preprocess(string s, int a[])
	{
		int i=1;
		int j=0;
		while(i < s.length())
		{
			if(s[i] == s[j])
			{
				a[i] = j+1;
				i++;
				j++;
			}
			
			else if(j > 0)
				j = a[j-1];
			
			else
			{
				a[i] = 0;
				i++;
			}
		}
	}
};
